2001-2002: Nhà vô địch Tây Ban Nha

Năm 2001 Benítez được bổ nhiệm làm huấn luyện viên Valencia CF thay thế Hector Cuper. Câu lạc bộ trước đó đã tiếp cận Javier Irureta, Mané và Luis Aragonés nhưng đều thất bại. Tuy nhiên chủ tịch câu lạc bộ Javier Subirats đã nhận ra khả năng của Benítez và ủng hộ việc bổ nhiệm ông. Bất chấp mất cả Gaizka Mendieta và Claudio López, ông vẫn thừa hưởng từ Cuper một đội bóng đầy tiềm năng. Santiago Cañizares, Roberto Ayala, Rubén Baraja, David Albelda và Pablo Aimar đã tạo nên trục xương sống cho một đội bóng mạnh nhưng chưa đáp ứng được sự kỳ vọng.

Người hâm mộ Valencia CF đã bị lôi cuốn bởi phong cách tấn công mạnh mẽ mà Benítez truyền cho các học trò. Ông cũng biết cách sử dụng Mista và Curro Torres. Mista trở thành chân sút hàng đầu của Valencia với 19 bàn thắng trong mùa giả 2003-04 còn Curro Torres đã vươn lên đẳng cấp quốc tế. Năm 2002, lối chơi này đã giúp Benítez đưa Valencia CF đến danh hiệu La Liga đầu tiên sau 31 năm với khoảng cách 7 điểm so với đội thứ hai Deportivo de La Coruña.

Tuy vậy mùa giải tiếp theo 2002-03 là một nỗi thất vọng khi câu lạc bộ thất bại trong việc bảo vệ danh hiệu, học kết thúc mùa giải với vị trí thứ 5 kém nhà vô địch Real Madrid 18 điểm. Mùa giải này cũng chứng kiến trận ra mắt của Benítez tại UEFA Champions League. Valencia vào tới tứ kết trước khi để thua Inter Milan.

2003-2004: Cú đúp La Liga/UEFA Cup

Mùa giải 03-04 là một câu chuyện khác. Valencia CF vô địch La Liga trước 3 vòng đấu và đánh bại Marseille 2-0 trong trận chung kết UEFA Cup. Bất chấp thành công này, Benítez đã có bất hòa với Jesus Garcia Pitarch, giám đốc thể thao của câu lạc bộ trong việc mua sắm cầu thủ và thất bại của câu lạc bộ trong việc củng cố đội hình. Sự khác biệt về quan điểm khiến Benítez từ chức vào tháng 6-2004. Ông nổi tiếng với câu nói: " Tôi yêu cầu một cái bàn và họ mua cho tôi một cái chụp đèn" khi được hỏi về những cầu thủ ông muốn mua.